package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test
import java.util.*

/*
 https://leetcode.cn/problems/path-sum/description/
 https://programmercarl.com/0112.%E8%B7%AF%E5%BE%84%E6%80%BB%E5%92%8C.html

 112. 路径总和
 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
 叶子节点 是指没有子节点的节点。


示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。

示例 2：
输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。

示例 3：
输入：root = [], targetSum = 0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。
 */
class leetcode_112 {
    @Test
    fun test_1() {
        // [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22

        val root = TreeNode(5)
        val n4 = TreeNode(4)
        val n8 = TreeNode(8)
        val n11 = TreeNode(11)
        val n13 = TreeNode(13)
        val n4_v2 = TreeNode(4)
        val n7 = TreeNode(7)
        val n2 = TreeNode(2)
        val n1 = TreeNode(1)
        root.left = n4
        root.right = n8
        n4.left = n11
        n8.left = n13
        n8.right = n4_v2
        n11.left = n7
        n11.right = n2
        n4_v2.right = n1

        val actual = hasPathSum(root, 22)
        val expect = true
        Assert.assertEquals(expect, actual)
    }

    @Test
    fun test_2() {
        val root = TreeNode(5)
        root.left = TreeNode(2)
        root.left = TreeNode(3)
        val actual = hasPathSum(root, 22)
        val expect = false
        Assert.assertEquals(expect, actual)
    }

    @Test
    fun test_3() {
        val actual = hasPathSum(null, 0)
        val expect = false
        Assert.assertEquals(expect, actual)
    }

    private fun hasPathSum(root: TreeNode?, targetSum: Int): Boolean {
        // return hasPathSum1(root,targetSum)
        if (null == root) {
            return false
        }
//        return hasPathSum2(root, targetSum - root.`val`)
        return hasPathSum3(root, root.`val`, targetSum)
    }

    private fun hasPathSum1(root: TreeNode?, targetSum: Int): Boolean {
        // 深度遍历 - 前序 - 迭代
        // 结束条件：左孩子和右孩子为空，说明这条线路已经遍历完了
        // T - N
        // S - N
        if (null == root) {
            return false
        }

        val stack: LinkedList<Triple<TreeNode, Int, Boolean>> = LinkedList<Triple<TreeNode, Int, Boolean>>()
        stack.push(Triple<TreeNode, Int, Boolean>(root, root.`val`, false))
        while (!stack.isEmpty()) {
            val triple: Triple<TreeNode, Int, Boolean> = stack.pop()
            val node: TreeNode = triple.first
            val sum: Int = triple.second
            val visited: Boolean = triple.third
            if (visited) {
                // 结束条件
                if (node.left == null && node.right == null) {
                    if (sum == targetSum) {
                        return true
                    }
                }
                continue
            }
            // 右
            node.right?.let {
                stack.push(Triple<TreeNode, Int, Boolean>(it, sum + it.`val`, false))
            }
            // 左
            node.left?.let {
                stack.push(Triple<TreeNode, Int, Boolean>(it, sum + it.`val`, false))
            }
            // 中
            stack.push(Triple<TreeNode, Int, Boolean>(node, sum, true))
        }
        return false
    }

    private fun hasPathSum2(root: TreeNode?, n: Int): Boolean {
        // 深度遍历 - 前序遍历 - 递归
        // T - N
        // S - N

        // 结束条件
        if (null == root) {
            return false
        }
        // 中
        if (root.left == null && root.right == null) {
            // TODO : 此处条件 是 0 == n
            if (0 == n) {
                return true
            }
        }

        var num: Int = n
        // 左
        root.left?.let {
            num = num - it.`val`
            val isMatched = hasPathSum2(it, num)
            num = num + it.`val`
            if (isMatched) {
                return true
            }
        }
        // 右
        root.right?.let {
            num = num - it.`val`
            val isMatched = hasPathSum2(it, num)
            num = num + it.`val`
            if (isMatched) {
                return true
            }
        }
        return false
    }

    private fun hasPathSum3(root: TreeNode?, sum: Int, targetSum: Int): Boolean {
        // 深度遍历 - 前序遍历 - 递归
        // T - N
        // S - N

        // 结束条件
        if (null == root) {
            return false
        }
        // 中
        if (root.left == null && root.right == null) {
            if (sum == targetSum) {
                return true
            }
        }

        var num: Int = sum
        // 左
        root.left?.let {
            num = num + it.`val`
            val isMatched = hasPathSum2(it, num)
            num = num - it.`val`
            if (isMatched) {
                return true
            }
        }
        // 右
        root.right?.let {
            num = num + it.`val`
            val isMatched = hasPathSum2(it, num)
            num = num - it.`val`
            if (isMatched) {
                return true
            }
        }
        return false
    }
}